class Solution {
public:
    static const int mod = 1e9+7;    
    vector<int> ss{2,3,5,7,11,13,17,19,23,29};                                 
    int numberOfGoodSubsets(vector<int>& nums) {
        int n = nums.size();
        int mask = 1 << 10;
        vector<int> arr(31);
        for(int i = 0;i < n;i++){
            arr[nums[i]]++;
        }
        
        vector<long long> dp(mask);
        dp[0] = 1;
        
        for(int i = 2;i <= 30;i++){
            if(arr[i] == 0) continue;
            
            bool ok = true;
            int u = 0;
            int x = i;
            
            for(int j = 0;j < 10 && ok;j++){
                int cnt = 0;
                while(x % ss[j] == 0){
                    u |= (1<<j);
                    x /= ss[j];
                    cnt++;
                }

                if(cnt > 1){
                    ok = false;
                }
            }

            if(!ok) continue;
           
            
            for(int state = 0;state < mask;state++){
                
                if((state & u) != 0) continue;
                
                dp[state|u] = (dp[state|u] + dp[state]*arr[i]%mod)%mod;
            }
        }
        
        long long ans = 0;
        for(int i = 1;i < mask;i++){
            ans = (ans + dp[i]) % mod;
        }
        for(int i = 0;i < arr[1];i++){
            ans = ans * 2 % mod;
        }
        return ans;
    }
};
